COMMENT ⊗   VALID 00004 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification = \magstephalf
C00004 00003
C00009 00004	\ppskip
C00014 ENDMK
C⊗;
\magnification = \magstephalf
\catcode`|=13
\def|#1|{\hbox{\it#1\/}}
\parindent 0pt
\parskip 0pt
\def\pskip{\penalty-1000\vskip 6pt plus 2pt minus 1pt}
\def\ppskip{\penalty-2000\vskip 10pt plus 3pt minus 2pt}
\def\no(#1){\noindent\hbox to 6em{(#1)\hfill}}
\catcode`⊗=13
\def⊗{\hbox to 2em{}}
\def\IF{\mathop{\bf if}}
\def\THEN{\mathrel{\bf then}}
\def\ELSE{\mathrel{\bf else}}
\def\AND{\mathrel{\bf and}}
\def\OR{\mathrel{\bf or}}
\def\NOT{\mathop{\bf not}}
\def\N{\mathop{\bf n}}
\def\T{\hbox{\tt T}}
\def\NIL{\hbox{\tt NIL}}
\def\.{\mathbin{.}}
\def\A{\mathop{\bf a}}
\def\D{\mathop{\bf d}}
\def\EQ{\mathrel{\bf eq}}
\def\AT{\mathop{\bf at}}
\def\quote#1{\hbox{\sfcode`.=1000\tt#1}}
\def\list#1{\langle#1\rangle}

\centerline{CS 206---Recursive Programming and Proving}
\centerline{Homework 1 Solutions}
\centerline{Thursday, October 20, 1983}


\ppskip
{\bf Solutions}:
More than one solution is given for some of the problems; in
such cases the preferred answer is first.

\ppskip
\no(1)$|samelength|[u,v] ←$\par
$⊗⊗⊗⊗\IF\N u\OR\N v\THEN\N u\AND\N v$\par
$⊗⊗⊗⊗\ELSE |samelength|[\D u,\D v]$\par
\pskip
$⊗⊗⊗|samelength|[u,v] ←$\par
$⊗⊗⊗⊗\IF\N u\THEN\N v$\par
$⊗⊗⊗⊗\ELSE\IF\N v\THEN\NIL$\par
$⊗⊗⊗⊗\ELSE |samelength|[\D u,\D v]$

\ppskip
\no(2)$|prup|[u,v]←$\par
$⊗⊗⊗⊗\IF\N u\THEN\NIL$\par
$⊗⊗⊗⊗\ELSE (\A u\.\A v)\.|prup|[\D u,\D v]$\par
\pskip
In this problem (as well as in the others) it was OK to assume that the input
was reasonable, i.e.\ that $u$ and $v$ have the same length.  Some people
checked for cases where this did not hold and caused some default action, for
example
$$|prup|[\quote{(A B C)},\quote{(1 2)}]=\quote{((A . 1) (B . 2) C)}.$$
Another possibility is to terminate when $\N u\OR\N v$.  Terminating on
$\N u\AND\N v$ is inappropriate---if you are assuming that
the lists are the same length then $\N u$ is sufficient, but if
the lists are of different length then you
may end up taking the |cdr| of \NIL.

\ppskip
\no(3)$|istail|[u,v]←(u=v)\OR(\NOT\N v)\AND|istail|[u,\D v]$\par
\pskip
$⊗⊗⊗|istail|[u,v]←$\par
$⊗⊗⊗⊗\IF u=v\THEN\T$\par
$⊗⊗⊗⊗\ELSE\IF\N v\THEN\NIL$\par
$⊗⊗⊗⊗\ELSE|istail|[u,\D v]$\par
\pskip
A common mistake here was to test $\N v$ before $u=v$.  The test for
$u=v$ must come first, since we want $|istail|[\NIL,\NIL]$ to be \T.
Incidentally, the external notation $u=v$ is an abbreviation for
$|equal|[u,v]$, or \quote{(EQUAL U V)} in internal form; and $u\EQ v$
is the external-form abbreviation for $|eq|[u,v]$, which is
\quote{(EQ U V)} internally.

\ppskip
\no(4)$|commontail|[u,v]←$\par
$⊗⊗⊗⊗\IF|istail|[u,v]\THEN u$\par
$⊗⊗⊗⊗\ELSE|commontail|[\D u,v]$\par
\pskip
The above definition is nice and simple, and it works!  Some people
started with the test $\IF\N u\THEN\NIL$, which is not needed since
|istail|, if correctly written, handles this case.  Most other solutions
involved |reverse|.  The one on page 161 of the book is the best of those
(though you weren't supposed to have read that far);

\ppskip
\no(5)$|upto|[u,v]←$\par
$⊗⊗⊗⊗\IF u=v\THEN\NIL$\par
$⊗⊗⊗⊗\ELSE\A v\.|upto|[u,\D v]$\par

\ppskip
\no(6)$|mapapp|[f,u]←$\par
$⊗⊗⊗⊗\IF\N u\THEN\NIL$\par
$⊗⊗⊗⊗\ELSE f[\A u]*|mapapp|[f,\D u]$\par
\pskip
When you implement this in MacLisp, if you try to say \quote{(F (CAR U))}
for $f[\A u]$, you may get an error message.  There are at least three ways
out of this:\quad (1) say \quote{(FUNCALL F (CAR U))},\quad (2) say
\quote{(APPLY F (LIST (CAR U)))},\quad or (3) incant \quote{(SSTATUS PUNT NIL)}
to MacLisp and then you will be able to say \quote{(F (CAR U))}.  The
third option makes MacLisp actually do what early versions used to do,
namely, when there is no function definition for \quote{F}, it
evaluates it.  Method (1) is preferable, though, since it is closer to
what may be found in other dialects of LISP.

\ppskip
\no(7)$|mapchoose|[p,u]←$\par
$⊗⊗⊗⊗\IF\N u\THEN\NIL$\par
$⊗⊗⊗⊗\ELSE\IF p[\A u]\THEN\A u\.|mapchoose|[p,\D u]$\par
$⊗⊗⊗⊗\ELSE |mapchoose|[p,\D u]$\par
\ppskip
{\bf grading:}
As this was the first assignment, and many people were not familiar with
the format intended, the grading on this assignment was more or less
pass/fail, where the only thing that was taken notice of was the number
of questions seriously attempted. In the coming cases, we will expect
people to hand in more complete work, i.e. assignments with no external
notation will not be graded, and serious testing will be expected.

\ppskip
{\bf Testing:}
Testing is an important part of debugging. In general, testing has two
main goals : the more trivial one is just seeing ( and showing) that 
the program does what is intended on a few `standard' or `random' cases.
The other, which in many cases will discover unexpected bugs, is the
testing of {\it boudary} cases. Boundary cases in this 
assignment were those in which some of the arguments (or both) were 
\NIL . There were students who defined, say, $istail$ or $samelength$
incorrectly in case one of the arguments was \NIL , and never found
out about it because of inappropriate testing.
In general, boundary cases may have other interpretations, such as
cases where the program is supposed to compute in a way different
from the ordinary, because of some specific property of the data.
It is worthwhile to spend some time making up the right test data,
because it may prevent subtle bugs.

\vfill\end